这是一篇一直想写的总结. 主要是复习的时候详细复习(这里应该说是学习了..)了一下最短路径问题. 发现当年学的还有很多不足.. 很多算法没学过,学过的算法的局限性我也不知道.

就像当年数据结构上机,练习dijkstra算法,虽然我自己敲了出来,但是学长问我这个能不能处理负权边的问题的时候我还是不知道..

这里就以负权边为索引详细说一下几个最短路径算法..

1. Dijkstra算法

这个应该比较熟悉了,所有的涉及到最短路径的问题都会提到这个算法. 算法原理是贪心 解决单源最短路径问题

先选择一个源点,也就是路径的起点. 然后重复 k 轮,每一轮添加一个点到目前生成的树里面,所以 k 是除源点外节点的数目 每一轮中分为两步

1. 选择 : 选择源点到达距离最短的点当做下一个加入生成树里面的点
2. 更新 : 由刚刚选择的点更新源点到每个点的距离

其中.选择这一步跟时间复杂度有点关系

1. 比较朴素的方法,既然要选最小的,那就遍历一遍
   • 这种方法在图比较稠密的时候比较好用,时间复杂度为:
2. 既然要找最小的,建一个最小堆就可以了,这样时间复杂度好像比较低
   • 实际上这样做的话比较复杂,时间复杂度也不一定低.
   • 复杂点 1 在堆里面要存一对元素(pair),因为我们需要距离这个值来进行比较,维护这个堆,还需要最小的距离对应的节点的编号,因为后面我们需要找到这个节点进行更新
   • 复杂点 2 在于这个堆不是一成不变的,而需要更新,每次更新的时候都涉及堆结构的变化,会带来额外的复杂度
   • 这种方法在图比较稀疏的时候比较好用,时间复杂度为:

最后,这个算法没有办法解决负权边的问题 因为上文提到,这个算法逐步生成一棵树的,而每一步新生成的节点都代表了源点到它的最短路径. 如果有负权边的话,上面那句话就无法保证,有可能会出现后面的一条负权边导致前面已经生成完毕的树里面的某个点遭到破坏

2. Bellman-Ford算法

这个算法有改进,权值可以为负

dist k[u] 代表最多经过 k 条边,源点到 u 的最短距离

dist n[u] 就是源点到 u 的最短距离, n 为顶点数(因为最短路径边数目小于顶点数,没有负权环)

可以得到推导式

dist k[u] = min{dist k-1[u], min{dist k-1[j] + E[j][u] } }

由源点最多经过 k 条边,到 u 的最短距离是 { 最多经过 k-1 条边的最短距离 } 和 { 最多经过 k-1 条边到某个边的最短距离加上这个边到 u 的距离 }里面更小的那个

伪代码如下

1
2
3
4
5

for(k = 2 : n)
    for(u = 0 : n)
        for(i = 0:n)
            if(E[i][u] > 0 && dist[u] > E[i][u] + dist[i])
                dist[u] = E[i][u] + dist[i]

上面提到了,这个算法不允许图中有负权环 因为出现了负权环,就不存在最短路径问题了,一直在负权环上面循环可以使路径趋近于无穷小..

3.发现负权环

上面提到了负权环,如何判断图中有没有负权环呢?

先看看如何发现环 可以进行一波深度优先搜索,如果发现搜索的过程中搜索到了已经搜到了的元素,就有环 或者进行一下拓扑排序,如果运行到最后还有元素,就能判断有环

由于和题目不太相关,这里先不多说了

4.Floyd算法

上面说了单源最短路径的算法,这里说一个多源的,就是求出整个图上每两点之间的最短路径

A ij[k] 代表从 i 到 j ,中转点序号小于等于 k 的最短路径

A ij[n] 就是从 i 到 j 的最短路径, n 为节点的数目,也就是节点序号的最大值

可以得到推导式

A ij[k] = min{ A ij[k-1] , A ik[k-1] + A kj[k-1]}

从 i 到 j ,中转点序号小于等于 k 的最短路径等于 { 中转点序号小于 k-1 的最短路径 } 和 { 中转点序号最大为 k 的最短路径(中转点包含k) }里面最小的一个

总结结束.. 今天看到了一个有趣的单词 redraw re-draw 重画 我一开始看成了 red-raw 红红的原始的..